#include "calculate.h"

/**********************************************
 *
 *  This function tries to open a file. Returns
 *  True on success and false on failure.
 *  Taken from a simple google query.
 *
 *  Author: Oxyd form gamedev ^.^
 *
 ************************************************/
int file_exists(char* filename)
{
	FILE* file;
	if( (file = fopen(filename,"r")))//try to open
	{
		fclose(file);
		return TRUE;//Woot success
	}
	return FALSE;
}


//This function takes the input filename for the map, creates the map,
//and returns the created map as well as passing the number of nodes
//and edges back to main by address.
//
//Author: Michael Sickles
int** createMap(char* file_map,int* num_nodes,int* num_edges){
	int nodes;//num of nodes
	int edges;//num of edges
	int loc;
	int x_coor;//x coordinate
	int y_coor;//y coordinates
	FILE* fp;
	coor* coordinates; //store coordinates
	int** map;
	int i,j,dist;
	int node1,node2;
	fp = fopen(file_map,"r");
	fscanf(fp,"%d %d",&nodes,&edges);
	*num_nodes=nodes;
	*num_edges=edges;
	coordinates = malloc(nodes*sizeof(coor));
	for(i=0;i<nodes;i++){
                //read in coordinates
		fscanf(fp,"%d %d %d",&loc,&x_coor,&y_coor);
		coordinates[loc].x=x_coor;
		coordinates[loc].y=y_coor;

	}
	
	/*Create dynamic graph */
	map=malloc(nodes*sizeof(int*));
	for(i=0;i<nodes;i++)map[i]=malloc(nodes*sizeof(int));

	for(i=0;i<nodes;i++){
                for(j=0;j<nodes;j++){
			map[i][j]=-1;
		}
	}
	/* Create links locations on graph */
	for(i=0;i<edges;i++){
		fscanf(fp,"%d %d",&node1,&node2);
		dist = distance(coordinates[node1].x,coordinates[node1].y,coordinates[node2].x,coordinates[node2].y);
		map[node1][node2]=dist;
		map[node2][node1]=dist;
	}
	fclose(fp);
        free(coordinates);//give back memory
	return map;
}

//This function calculates the distance betwen two
//two-dimensional points
//
//Author: Michael Sickles and John Jachna
int distance(int x1,int y1,int x2, int y2){
	int dist;
        //distance formula
	dist = sqrt(pow((x2-x1),2) + pow((y2-y1),2));

	return dist;

}


//Given a graph, an start point, an end point, and the number
//of nodes in the graph, this function calculates the shortest
//path between the start and the end, and prints the
//distance and the path taken
//
//Author: Michael Sickles and John Jachna
void find_Path(int** map, int start, int end,int size)
{
	int min = -1;//infinitie
	int minLoc = start; //location of min
	int next = start;//next node
	int i,j;
	int enter = 0;
	path* trip;

	trip = malloc(size*sizeof(path));

	//initialize the trip array for keeping track of the
	for(i=0;i<size;i++){
		trip[i].node = -1;
		trip[i].weight = -1;
		trip[i].visited = 0;

	}
	//traverse down the map
	for(i=0;i < size; i++){
		trip[next].visited = 1;
		enter = 0;
		//printf("\n");

		//traverse across the map
		for(j=0;j<size;j++){

			//If we have not visited the node
			if(trip[j].visited == 0){
                                //if they are both infinities
				if(trip[j].weight == -1 && map[next][j] != -1){ 
                                        //if best dist of trip is infinitie
					if(trip[next].weight == -1){

						trip[j].node = next;
						trip[j].weight = map[next][j] + trip[next].weight + 1;

					}else{
                                            //other wise reset best distance
						trip[j].node = next;
						trip[j].weight = map[next][j] + trip[next].weight;
					}
                                        //compare if current dist is greater than if going down this trip
				}else if(trip[j].weight >  (trip[next].weight + map[next][j]) && map[next][j] != -1){
                                       //if yes replace
					trip[j].node = next;
					trip[j].weight = map[next][j] + trip[next].weight;

				}

                                
                                //reset initialization to find minimum path of all our paths

				if(enter == 0){
					enter = 1;
					min = trip[j].weight;
					minLoc = j;
                                        //if our min is greater than a trip weight, reset it to  other weight
				}else if(((min > trip[j].weight) && (trip[j].weight != -1)) || (min == -1)){
					min = trip[j].weight;
					minLoc = j;

				}
			}

		}
		next = minLoc;



	}
	next = end;
	printf("\n");
	i=0;
	
	if(trip[end].weight == -1)
	{
		printf("The shortest distance from node %d to node %d is %d.\n", end, start,0);
		printf("The shortest path from node %d to node %d is %d -> %d\n", end, start, end,start);
	}else{
		printf("The shortest distance from node %d to node %d is %d.\n", end, start, trip[end].weight);
		printf("The shortest path from node %d to node %d is %d", end, start, end);
		while(next != start && i < size){
                    //follow path backwards from end to start and find path. 
                    //we actually reversed so it finds path from start to end
                    //this saved us space by doing it this way
			next = trip[next].node;
			printf(" -> %d", next);
			i++;
		}
		printf("\n");
	}        
	
	free(trip); //not my memory
}


void queryFile(char* filename, int** map, int numNodes)
{
	int numQueries, i, start, end;
	FILE* fp;
        //open file and read in num queries	
	fp = fopen(filename, "r");
	fscanf(fp, "%d", &numQueries);
	
	for(i = 0; i < numQueries; i++)
	{
		fscanf(fp, "%d %d", &start, &end);
                //read in start and end, send backwards
                //Since Undirected it makes printing easier
		find_Path(map, end, start, numNodes);
	}
	fclose(fp);
}



/****************************************************************/





int main(){

	char file_map[31];
	char file_query[31];
	int num_nodes,num_edges;//numbers about graph
	int** map;//map of weights

        //read in map file
	printf("Please enter the name of the Map File: ");

        scanf("%s",file_map);
	if(!file_exists(file_map)){
		printf("Error: File %s does not exsist\n",file_map);
		exit(FILE_ERROR);
	}
     //read in query file
	printf("Please enter the name of the Query File: ");
	scanf("%s",file_query);
	if(!file_exists(file_query)){
		printf("Error: File %s does not exsist\n",file_query);
		exit(FILE_ERROR);
	}
        //create the map
	map = createMap(file_map,&num_nodes,&num_edges);
        //query the map
	queryFile(file_query,map,num_nodes);
	return 0;
}
